Error correcting codes are widely used in communications systems. A reference book for coding in connection with communications systems is R. D. Gitlin, J. F. Hayes and S. B. Weinstein, “Data Communication Principles”, 1992 Plenum Press, New York, ISBN 0-306-43777-5, which is incorporated herein by reference. Chapter 3 gives a description of error correcting and detecting codes and provides references to many other sources of information in the field. In the field of communications, source information is transmitted or stored into an imperfect medium. A receiver recovers the source information which may be corrupted by errors due to the imperfect medium. Error correcting codes have been developed that add redundancy to transmitted information, enabling correction of errors in the remote receiver.
Existing error correcting codes are commonly defined for finite Galois fields GF(mn) with mn elements, where m is a prime number and n is an arbitrary integer. The field GF(mn) defines arithmetic modulo-m or with modulus m. Most practical codes are binary codes using modulus 2 and modulo-2 exclusive- or operations. The Reed-Solomon codes defined in GF(2n) are an exception. My invention described in this document addresses codes defined on GF(mn) where m is a number greater than 2. These codes will operate on symbols having m elements or m states. This is beneficial for efficiently transmitting or storing information in media having m states. The data may originate from a source that has m states or a modulus converter can be used to convert a stream of binary data into modulus-m symbols. Each symbol then carries log2(m) bits of information.
The public switched telecommunications network (PSTN) is one example of a transmission media having m non-binary states. The PSTN uses pulse code modulation (PCM) having at most 256 levels where many of the levels are known to be unreliable. A V.90 modem operates in this system by using a modulus converter to convert PCM samples into m typically non-binary levels that can be reliably resolved.
Most data sources do not have a natural binary unit of measure. Time is measured in units of 12 hours, 60 minutes, and 60 seconds. Angles are measured in units of 2Π radians or 360 degrees. Although, of practical necessity alternate units of measure may be developed such as the original 16 (24 binary) points of a compass and digital resolvers that measure the fractional parts of a circle in bins.
In other examples, molecules may be used to store information in molecular combinations that may have m states. Reliable semaphore signaling may have m=3 states such as left, right or overhead. The 3 railroad semaphore states are proceed, caution or stop, equal to the common traffic light. There are 3 common phase states of matter: solid, liquid, and gaseous.
Quantum mechanical systems may use entangled photons, qubits, qudits or particle spin states to carry information in an optimum number of states m that is not a power of 2. A quantum qutrit is a unit of quantum information in a 3-level quantum system and a qudit is a unit of quantum information in a d-level (or modulus d) quantum system. Qudit detection systems are described in U.S. Pat. No. 7,038,188 titled “Non-demolition photon detector that preserves input state characteristics”, U.S. Patent application 20070145271 titled “Quantum information conversion between matter and light representations”, U.S. Patent application 20060056631 titled “Tests of quantum information” and U.S. Patent application 20050078902 titled “Photonic interconnect system,” which are all incorporated herein by reference. Various qudit representations are described in U.S. Patent application 20050254823 titled “Quantum optical state converter,” which is incorporated herein by reference. U.S. Pat. No. 5,768,297 titled “Method for reducing decoherence in quantum computer memory”, which is incorporated herein by reference, describes qubit manipulation methods that avoid or correct decoherence and allow for error correction without disturbing the superposition of states represented by the qubits.
Prior art computer code that implements Reed-Solomon error correction encoding and decoding functions is presented in, for example, U.S. Pat. No. 5,602,382 titled, “Mail Piece Bar Code Having A Data Content Identifier,” which is incorporated herein by reference. In this example the 26 letters of the alphabet plus 10 numeric digits are encoded by 3 bars each treated as 2 bits into 6-bit elements of a Reed-Solomon (RS) code. Of course, a modulo 36 system would suffice.
Furthermore, “block codes” are error correcting codes that operate on a fixed size block of digital information. Examples of block codes are parity check codes, Hamming codes and Bose-Chaudhuri-Hocquenghem (BCH) codes. Digital information is transmitted or stored in units or symbols which may contain single digital data bits of information or multiple digital data bits of information. Block codes combine a fixed number of source data symbols and a fixed number of redundant symbols into a coded block containing a fixed number of coded symbols. The coded block of coded symbols is referred to as a “codeword” and the redundant symbols are referred to as “parity symbols”. A block encoder is a device that accepts a fixed number of source data symbols, computes redundant parity symbols relating to the source data symbols and outputs a coded block, or codeword, containing the source data symbols and redundant parity symbols.
Various coding algorithms are available or may be developed for computing the redundant parity symbols. Coding algorithms can be differentiated by the ratio of redundant symbols to source symbols, complexity of encoding, complexity of decoding, number of errors that can be corrected, type of errors that can be corrected, etc. A block decoder is a device that receives the coded block, or codeword, corrects errors in the source symbols, and outputs the corrected source symbols, while discarding the redundant parity symbols.
There is another type of error correcting code known as a “convolutional” error correcting code. The convolutional code operates on a sequence of source symbols to generate an output sequence with additional redundant information. A convolutional encoder is a sequential circuit with memory of previous symbols. Each output symbol is related to all previous symbols, unlike the block encoder, which generates coded blocks, or codewords, that are completely independent of previous blocks or codewords.
Forward error correction (FEC) systems are used in many data communication and storage systems today. These systems “forward” redundant information to the remote receiver to facilitate “error correction.” Systematic codes typically transmit unmodified user source data directly in a block with appended redundant parity information at the end of the block. The encoded block of source data and parity information is commonly known as a “codeword.” A decoder in the remote receiver utilizes the redundant information to correct errors that may have occurred during transmission.
FEC codes are selected for properties that benefit specific applications. Hamming codes and Bose-Chaudhuri-Hocquenghem (BCH) codes are two of many examples. The popular Reed-Solomon (RS) codes are a subclass of BCH codes. Many FEC systems implement concatenated codes, such as a RS block code concatenated with a convolutional trellis code. Block codes, such as the Hamming, BCH, and RS codes, can correct multiple errors that may occur in a block of data. Most codes are designed to correct random errors, although some codes are designed to correct burst errors that occur on sequential symbols. Burst error events may cause a large number of errors in a single block. In burst error environments, the FEC system may include an interleaved block code concatenated with a distributed trellis encoder. The FEC block codes encode k source data symbols into a fixed block or codeword of n symbols containing p redundant parity check symbols where p=n−k. RS codes can correct up to p/2 random symbol errors in a block of n symbols. A burst of errors in excess of the error correcting capacity of the code (p/2) will cause the FEC decoder to fail, resulting in errors in the decoded block. Interleaving methods are used to interleave the blocks dispersing the symbols of each encoded block over a large number of blocks. The interleaved blocks are transmitted into or stored in a communication medium susceptible to burst error events. A deinterleaver in the receiver reassembles the encoded blocks, while beneficially dispersing the burst errors among many blocks. Each block then has fewer errors and these can be reliably corrected by the code.
Interleavers, such as a convolutional interleaver, are used in the art to disperse burst errors. A convolutional interleaver may pass coded symbols through B sections or branches of increasing delay. Each section has delay increasing in steps of M symbols. The first section has a delay of zero and the last section has a delay of M*(B−1) symbols. Thus, adjacent symbols from any codeword are separated by B symbol periods at the interleaver output. This convolutional interleaver can protect against error burst durations of B symbol periods. For a block or codeword size of n symbols and M*B greater than or equal to n, a burst duration less than M*B symbol periods will result in no more than M errors in the interleaved block. The deinterleaver operates in the reverse order passing the first received symbol through a delay section of M*(B−1) symbols and the next received symbols through sections having M fewer delayed symbols per section. The final received symbol is passed through a section with no delay. The total delay of combined interleaver and deinterleaver is then M*(B−1) symbol periods for all symbols.
Conventional interleaving methods have undesirable side effects. Conventional interleavers delay the data prior to transmission and scramble the original order of the source data. The reordered source symbols yield unrecognizable data at remote receivers unless they are deinterleaved. A deinterleaver is required in the receiver to reassemble the data in the correct order for decoding. The deinterleaver adds undesirable additional delay and typically must be synchronized with the remote interleaver. The codeword symbols are spread out in the channel over M*B*(B−1) symbol periods. The final decoding of the full codeword is delayed by M*B*(B−1)+n−1 symbol periods. The conventional interleavers and deinterleavers add complexity to equipment and usually require significant additional memory.
There is a need in the industry for better systems and methods for encoding symbols of non-binary modulus m and correcting burst errors. The inventor has discovered a new coding methodology that addresses, among other things, the correction of burst errors in non-binary systems.